package hihocode;

import java.util.Scanner;

public class PackageProblem {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n, m;
		int[] values;
		int[] needs;
		n = scanner.nextInt();
		m = scanner.nextInt();
		values = new int[n];
		needs = new int[n];
		for(int i = 0; i < n; i++){
			needs[i] = scanner.nextInt();
			values[i] = scanner.nextInt();
		}
		getValues(needs, values, m);
		scanner.close();
	}
	
	//01背包问题
	private static void getValues2(int[] needs, int[] values, int m){
		int[][] dp = new int[needs.length][m + 1];
		//dp init
		if(needs[0] <= m){
			dp[0][needs[0]] = values[0];
		}
		int n = needs.length;
		for(int i = 1; i < n; i++){
			for(int j = 1; j <= m; j++){
				if(j >= needs[i]){
					dp[i][j] = Math.max(dp[i - 1][j - needs[i]] + values[i], dp[i - 1][j]);
				}else{
					dp[i][j] = dp[i - 1][j];
				}
			}
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j <= m; j++) {
				System.out.print(dp[i][j] + "  ");
			}
			System.out.println();
		}
		//不一定要使用完所有的券
		int res = 0;
		for(int j = 0; j < m; j++){
			res = Math.max(res, dp[n - 1][j]);
		}
		System.out.println(res);
	}
	
	
	// 01背包问题
	private static void getValues(int[] needs, int[] values, int m) {
		int[] dp = new int[m + 1];
		// dp init
		if (needs[0] <= m) {
			dp[needs[0]] = values[0];
		}
		int n = needs.length;
		for (int i = 1; i < n; i++) {
			for (int j = m; j >= 1; j--) {
				if (j >= needs[i]) {
					dp[j] = Math.max(dp[j - needs[i]] + values[i],
							dp[j]);
				}
			}
		}
//		for (int j = 0; j <= m; j++) {
//			System.out.print(dp[j] + "  ");
//		}
//		System.out.println();
		// 不一定要使用完所有的券
		int res = 0;
		for (int j = 0; j < m; j++) {
			res = Math.max(res, dp[j]);
		}
		System.out.println(res);
	}
}
